package leetcode.tree;

public class MorrisPre {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }
    public static void process(Node head){
        if (head == null){
            return;
        }

        Node cur = head;
        Node mostRight = null;

        while (cur!=null){
            mostRight = cur.left; //mosRight访问cur的左孩子

            if (mostRight != null){//说明有左孩子
                while (mostRight.right!=null && mostRight.right!=cur){//mostRight有右孩子不是空且不是cur
                    mostRight = mostRight.right;//mostRight向右一步走
                }
                //mostRight来到最右处
                if (mostRight.right == null){//第一次来到cur
                    mostRight.right = cur;//让mostRight的右子树指向cur所在位置
                    cur = cur.left;//cur向左一步
                    continue;
                }else {
                    mostRight.right = null;
                }
            } else {
                System.out.print(cur.value + " ");
            }
            cur = cur.right;
        }
    }
}
